After we outlined the basic functionality of matrix grammars, this chapter  describes how we can achieve more control on the parallel application of the vertical grammars. It is therefore necessary to recapitulate the results from \cite{sironmoney1977parallelsequential}. In this approach, tables are used to restrict the usage of vertical production rules. 

\begin{definition}
	$G = (G_H, G_V)$ is called a \emph{tabled context-sensitive matrix grammar} (\mbox{TCSMG}) (\emph{tabled context-free matrix grammar} (TCFMG), \emph{tabled regular matrix grammar} (TRMG) ), where
	\begin{compactitem}
		\item $G_H = (N_H, I, P_H, S)$ is a context-sensitive grammar (context-free grammar, regular grammar). This is similar to Definition~\ref{grammars_definition_xmg}. 
		\item $G_V = (\bigcup_{i = 1}^k G_{i}, \mathscr{P})$, where $G_{i} = (N_{i}, T, P_{i}, S_i)$ are right linear grammars where 
		\begin{compactitem}
			\item $T$ is a finite set of terminals,
			\item $N_{i}$ is a finite set of non-terminals ($N_{i} \cap N_{j} = \emptyset$ for $i \neq j$),
			\item $P_{i} = P_{Ni} \cup P_{Ti}$ are right-linear production rules, separated in two subsets consisting of non-terminal and terminal rules, 
			\item  $S_i$ is the start symbol and
			\item $\mathscr{P}$ is a finite set of tables. 
		\end{compactitem}
	\end{compactitem}
\end{definition}

Tables are non-empty subsets of $\bigcup_{i = 1}^k P_i$, but it is distinguished between non-terminal and terminal tables which only contain rules from $\bigcup_{i = 1}^k P_{Ni}$ and $\bigcup_{i = 1}^k P_{Ti}$ respectively. 

Derivations of tabled matrix grammars start with the start symbol $S$ and generate a string using the horizontal grammar $G_H$. The generated string contains intermediate symbols which are also the start symbols for the vertical grammars. The vertical derivation is now restricted in that way that only rules from the same table $t$ can be applied simultaneously. Therefore, we can have two different vertical derivations. At first let $t$ be a non-terminal table. Then 

\begin{center}
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
A_1 & \dots & A_n
\end{matrix}
\end{aligned}
}

$\overset{t}{\underset{G_V}{\Downarrow}}$

\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
a_{m1} & \dots & a_{mn} \\[-0.5ex]
B_1 & \dots & B_n
\end{matrix}
\end{aligned}
}

\end{center}
is a non-terminal derivation, where $(A_i \rightarrow a_{mi}B_i) \in t$ for $i = 1, \dots, n$. In the second case, $t$ is a terminal table and the derivation looks as follows: 

\begin{center}
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
A_1 & \dots & A_n
\end{matrix}
\end{aligned}
}

$\overset{t}{\underset{G_V}{\Downarrow}}$

\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
a_{m1} & \dots & a_{mn} \\[-0.5ex]
\end{matrix}
\end{aligned}
}

\end{center}
where $(A_i \rightarrow a_{mi}) \in t$ for $i = 1, \dots, n$. The reflexive, transitive closure of $\underset{G_V}{\Downarrow}$ is $\overset{*}{\underset{G_V}{\Downarrow}}$. 

Like before, we can define the language generated by a matrix grammar G:

\begin{definition}
	Let $G = (G_H, G_V)$ be a tabled context-sensitive matrix grammar (tabled context-free matrix grammar, tabled regular matrix grammar). The language generated by G is
	
	\[L(G) = \{p \in T^{*, *} \mid S \overset{*}{\underset{G_H}{\Rightarrow}} S_{i_1} \dots S_{i_{l_2(p)}} \overset{*}{\underset{G_V}{\Downarrow}} p\}\]
	
	and is called tabled context-sensitive matrix language (TCSML) (tabled context-free matrix language (TCFML), tabled regular matrix language (TRML)). 
\end{definition}

The family of TCSML (TCFML, TRML) is denoted by $\familyOf{TCSML}$ ($\familyOf{TCFML}$, $\familyOf{TRML}$). 

\begin{remark}
	In this definition, the sets of non-terminals of the vertical grammars are disjoint. If not, it is possible that more than one vertical grammar is used in the same column. But \cite{sironmoney1977parallelsequential} claims that the use of distinct non-terminals does not restrict the power of tabled matrix grammars. 
\end{remark}

Next, we will look at an example of a tabled matrix grammar to recognize the languages which can be generated. 

\begin{example}
\label{example_tabled_matrix_grammars}
	Let $G = (G_H, G_V)$ be a tabled matrix grammar with $G_H = (N_H, I, P_H, S)$, where
	\begin{compactitem}
		\item $N_H = \{S, M\}$ is the set of horizontal non-terminals,
		\item $I = \{S_1, S_2\}$ is the set of intermediates and
		\item $P_H = \{S \rightarrow S_1M, M \rightarrow S_2M, M \rightarrow S_1\}$. 
	\end{compactitem}
	The language generated by $G_H$ is $L(G_H) = \{S_1S_2^nS_1 \mid n \geq 0\}$. $P_H$ only contains right-linear rules. Hence, $G$ is a tabled regular matrix grammar. 
	
	The tuple $G_V$ contains two right-linear grammars $G_1$ and $G_2$ and a set of tables $\mathscr{P}$ where
	\begin{compactitem}
		\item $G_1 = (\{S_1\}, \{x\}, \{S_1 \rightarrow xS_1, S_1 \rightarrow x\}, S_1)$
		\item $G_2 = (\{S_2, A\}, \{., x\}, \{S_2 \rightarrow .S_2, S_2 \rightarrow xA, A \rightarrow .A, A \rightarrow .\}, S_2)$
		\item $\mathscr{P}$ contains
		\begin{compactitem}
			\item $t_1 = \{S_1 \rightarrow xS_1, S_2 \rightarrow .S_2\}$
			\item $t_2 = \{S_1 \rightarrow xS_1, S_2 \rightarrow xA\}$
			\item $t_3 = \{S_1 \rightarrow xS_1, A \rightarrow .A\}$
			\item $t_4 = \{S_1 \rightarrow x, A \rightarrow .\}$
		\end{compactitem}
	\end{compactitem}
	
	The languages generated by $G_1$ and $G_2$ are $L(G_1) = \{x^n \mid n \geq 1\}$ and $L(G_2) = \{.^nx.^m \mid n, m \geq 1\}$ respectively. 
\end{example}

The language generated by G contains pictures with the token H in it. We illustrate the generation of pictures in L(G) with an example of size (4, 5). 

\begin{center}
	\begin{longtable}{cc}
		$S \overset{*}{\Rightarrow} $  & \boxed{
			\begin{aligned}
				\begin{matrix}
					S_1 & S_2 & S_2 & S_2 & S_1 
				\end{matrix}
			\end{aligned}
		}\\ %new line of longtable
		& $\overset{t_1}{\Downarrow}$ \\ %new line of longtable
		& \boxed{
			\begin{aligned}
				\begin{matrix}
					x & . & . & . & x \\[-0.5ex]
					S_1 & S_2 & S_2 & S_2 & S_1 
				\end{matrix}
			\end{aligned}
		}\\ %new line of longtable
		& $\overset{t_1}{\Downarrow}$ \\ %new line of longtable
		& \boxed{
			\begin{aligned}
				\begin{matrix}
					x & . & . & . & x \\[-0.5ex]
					x & . & . & . & x \\[-0.5ex]
					S_1 & S_2 & S_2 & S_2 & S_1
				\end{matrix}
			\end{aligned}
		}\\ %new line of longtable
		& $\overset{t_2}{\Downarrow}$ \\ %new line of longtable
		& \boxed{
			\begin{aligned}
				\begin{matrix}
					x & . & . & . & x \\[-0.5ex]
					x & . & . & . & x \\[-0.5ex]
					x & x & x & x & x \\[-0.5ex]
					S_1 & A & A & A & S_1 
				\end{matrix}
			\end{aligned}
		}\\ %new line of longtable
		& $\overset{t_4}{\Downarrow}$ \\ %new line of longtable
		& \boxed{
			\begin{aligned}
				\begin{matrix}
					x & . & . & . & x \\[-0.5ex]
					x & . & . & . & x \\[-0.5ex]
					x & x & x & x & x \\[-0.5ex]
					x & . & . & . & x 
				\end{matrix}
			\end{aligned}
		}
	\end{longtable}
\end{center}

The hierarchy of the tabled matrix grammars is clear, due to the Chomsky hierarchy. We get $\familyOf{TRML} \subset \familyOf{TCFML} \subset \familyOf{TCSML}$. Furthermore, we get a hierarchy with the usual matrix grammars. 

\begin{theorem}
	$\familyOf{XML} \subset \familyOf{TXML}$ for X = R, CF or CS. 
\end{theorem}

\begin{proof}
	It is obvious, that $\familyOf{XML} \subseteq \familyOf{TXML}$ holds. That can be achieved, if $G_V$ only contains one table which contains every rule in $G_V$. The inclusion is proper because the language from Example~\ref{example_tabled_matrix_grammars} cannot be generated by a RLMG. This is not possible because the generation of a horizontal structure cannot be coordinated without tables. We have the same situation for context-free and context-sensitive languages. The corresponding horizontal languages are $L_{CF} = \{S_1^nS_2S_1^n \mid n \geq 1\}$ and $L_{CS} = \{S_1^nS_2S_1^nS_2S_1^n \mid n \geq 1\}$ \cite{sironmoney1977parallelsequential}, the vertical languages are the same as in Example~\ref{example_tabled_matrix_grammars}. 
\end{proof}

We are now going to have a look at the closure properties of tabled matrix grammars identified by \cite{sironmoney1977parallelsequential}. 

\begin{theorem}
	Each of the families of languages $\familyOf{TCSML}$, $\familyOf{TCFML}$, $\familyOf{TRML}$ is closed under 
	\begin{compactenum}
		\item union,
		\item horizontal concatenation and
		\item array and column homomorphism. An array homomorphism maps any symbol onto a picture of size $(r, s)$, where $r, s > 0$. Similarly, a column homomorphism maps a symbol onto a column of specified size.  
	\end{compactenum}
\end{theorem}

\begin{proof}
	%use this ~ to create a new line in the proof
	~ \begin{compactenum}
		\item The union of tabled matrix languages is clear, when we assume that the intermediate symbols of the horizontal grammar and the non-terminal symbols of the vertical grammars are distinct. 
		\item The idea is to create a grammar $G = (G_H, G_V)$ from $G_1 = (G_{H1}, G_{V1})$ and $G_2 = (G_{H2}, G_{V2})$. At first, $G_H$ must concatenate $G_{H1}$ and $G_{H2}$. This can be achieved by modifying the terminal rules from $G_{H1}$ and the starting rules from $G_{H2}$. Secondly, we must make sure that the vertical rules from $G_1$ and $G_2$ can be applied simultaneously. Therefore, each non-terminal table of $G_{V1}$ must be combined with each non-terminal table of $G_{V2}$. The same applies to the terminal tables. It can now be shown that $L(G) = L(G_1) \hcat L(G_2)$.
		\item This proof can be found in \cite{sironmoney1977parallelsequential}. 
	\end{compactenum}
\end{proof} 